package com.it.base.arithmetic.array;

/**
 * 通过稀疏数据来保存数据
 */
public class SparseArray {

    public static void main(String[] args) {
        //创建原始的二维数据为11*11
        int array [][] = new int [11][11];
        //假设二维数组中第3行第5列和第7行第9列有数据
        array[2][4] =1;
        array[6][8] =2;
        System.out.println("原始数据---------------------------------------------------------------------------开始");
        for (int [] row :array ) {
            for(int data :row){
                System.out.printf("\t"+data);
            }
            //换行,好观察原始数据
            System.out.println();
        }
        System.out.println("原始数据-----------------------------------------------------------------------------结束");

        //求原始数据中有几个值，在原始数据中，除了0(默认)之后的都是有效数据
        int sum = 0;
        for (int [] row :array ) {
            for(int data :row){
                if(data!=0){
                    sum++;
                }
            }
        }
        System.out.println("原始数据中的有效值一共有:"+sum+"个");
        //创建一个稀疏数组,一般来讲，稀疏数组的第1行第1列的值为原数组的i，第1行第2列的值为原数组的k,第1行第3列的值为原数组中一共有多少个有效值
        int [][] sparseArray = new int [sum+1][3];
        sparseArray[0][0]=11;
        sparseArray[0][1]=11;
        sparseArray[0][2]=sum;
        //遍历记录原数据中，值存放的位置
        int count=0;
        for (int i = 0;i<array.length;i++){
            for (int k = 0;k<array[i].length;k++){
                //判断是有值的情况
                if(array[i][k]!=0){
                    //第一行被占用
                    count++;
                    //向稀疏数组中记录原数组中有效值的分布情况
                    //原数组中第几行
                    sparseArray[count][0]=i;
                    //原数组中第几列
                    sparseArray[count][1]=k;
                    //存放的值
                    sparseArray[count][2]=array[i][k];
                }

            }

        }
        System.out.println("数组转为稀疏数组完成---------------------------------------------------------------------遍历稀疏数组开始");
        for(int [] row :sparseArray){
            for(int data :row){
                System.out.print("\t"+data);
            }
            System.out.println();
        }
        System.out.println("数组转为稀疏数组完成---------------------------------------------------------------------便利稀疏数组结束");
        System.out.println("稀疏数组转换数组 ---------------------------------------------------------------------开始");
        //首先通过稀疏数组的第一行来还原数组
        int newArray[][] =new int[sparseArray[0][0]][sparseArray[0][1]];
        //还原数组中的元素
        for(int i = 1;i<sparseArray.length;i++){
            newArray[sparseArray[i][0]][sparseArray[i][1]]=sparseArray[i][2] ;
        }
        System.out.println("稀疏数组转换数组 ---------------------------------------------------------------------结束");

        System.out.println("打印还原的数组 ---------------------------------------------------------------------开始");
        for(int [] row :newArray){
            for(int data:row){
                System.out.print("\t"+data);
            }
            System.out.println();
        }
        System.out.println("打印还原的数组 ---------------------------------------------------------------------结束");

    }
}
